Statement#

Suppose you are given a list of coins and a certain amount of money. Each coin in the list is unique and of a different denomination. You are required to count the number of ways the provided coins can sum up to represent the given amount. If there is no possible way to represent that amount, then return 0.

Note: You may assume that for each combination you make, you have an infinite number of each coin. In simpler terms, you can use a specific coin as many times as you want.

Let's say you have only two coins, 1010 and 2020 cents, and you want to represent the total amount of 3030 cents using these coins. There are only two ways to do this, you can use either of the following combinations:

  • 3 coins of 1010 cents: 10+10+10=3010+10+10=30.

  • 1 coin of 1010 cents and 1 coin of 2020 cents: 10+20=30.10+20=30.

Constraints:

  • 1 <= coins.length <= 300

  • 1 <= coins[i] <= 5000

  • All the coins have a unique value.

  • 0 <= amount <= 5000

Examples#

Let's see a few more examples to get a better understanding of the problem statement:

No.

Coins

Amount

Number of ways

1

[1, 2, 5]

7

6

2

[1, 5, 10, 25]

10

4

3

[7]

9

0

4

[9,10,11]

0

1

Try it yourself#

Implement your solution in the following playground.

Python
usercode > main.py
Input #1
Input #2
Coin Change II

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Unbounded Knapsack dynamic programming pattern.

Naive approach#

A naive approach to solve this problem would be to make all the possible combinations of coins or generate all subsets of coin denominations that sum up to the required amount.

While making the combinations, a point to keep in mind is that we should try to avoid repeatedly counting the same combinations. For example, 10+2010+20 cents add up to 3030 cents, and so do 20+1020+10. In the context of combinations, both these sequences are the same, and we will count them as one combination. We can achieve this by using a subset of coins every time we consider them for combinations. The first time, we can use all nn coins, the second time, we can use n1n−1 coins, that is, by excluding the largest one, and so on. This way, it is not possible to consider the same denomination more than once.

As a base case, we return 11 when the target amount is zero because there is only one way to represent zero irrespective of the number and kinds of coins available. Similarly, for the second base case, if at any point during our search for combinations, the remaining value needed to reach the total amount becomes less than zero, we return 00.

The slides below will help you visualize the process.

Created with Fabric.js 3.6.6

1 of 7

Created with Fabric.js 3.6.6 First, we check for all the possible combinations to make the target amount using coins up to a maximum value of 1, that is coin 1 only.

2 of 7

Created with Fabric.js 3.6.6 These are all the recursive function calls for coin 1.

3 of 7

Created with Fabric.js 3.6.6 Next, we check for all the possible combinations to make the target amount using coins up to a maximum value of 2, that is coins 1 and 2.

4 of 7

Created with Fabric.js 3.6.6 These are all the recursive function calls for coin 2.

5 of 7

Created with Fabric.js 3.6.6 Lastly, we check for all the possible combinations to make the target amount using coins up to a maximum value of 5, that is coins 1, 2 and 5.

6 of 7

Created with Fabric.js 3.6.6 Count all the leaves with amount = 0. There are 4 such leaves, thus our answer evaluates to 4.

7 of 7

Now, let's look at the code in the code widget below for the solution we just discussed.

Coin Change II using recursion

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

If the length of the list coins is nn, and the amount to be made out of them is CC, the time complexity of the recursive algorithm would be O(nC)O(n^C). This is because the maximum height of the call tree is CC, and there may be at most nn branches from each node in the call tree. Therefore, the total number of nodes in such a tree is bound by nCn^C. Therefore, the time complexity would be O(nC)O(n^C).

Space complexity#

The space complexity for this algorithm is O(C)O(C).

Optimized solution using dynamic programming#

As the recursive solution to this problem is very costly, let's see if we can reduce this cost in any way. Dynamic programming helps us avoid recomputing the same subproblems. Now let's analyze our recursive solution to see if it has the properties needed for conversion to dynamic programming.

  • Optimal substructure: If we wanted to find the solution to the problem of counting an amount, CC, given nn different coins, and we knew the answer to the nn subproblems formed by subtracting each of the nn coins from the amount CC, we could simply sum up the answer to these subproblems, and that would give us the answer to our original problem. Therefore, this problem obeys the optimal substructure property.

  • Overlapping subproblems: The algorithm solves the same subproblems again and again, so it also has the second property of dynamic programming.

Top-down solution#

The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating solutions to subproblems over and over again by storing the subproblem solutions, and reusing the stored solutions when the same subproblem is encountered again. Therefore, the only addition to this algorithm compared to the simple recursive one is the addition of memoization. We store all the results in memo and then retrieve them as needed. Since we had two defining variables here, the amount, and the maximum value, we use them to uniquely identify each subproblem.

Coin Change II using memoization

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

Let's see how many unique subproblems are possible that we can evaluate. The value of amount will not be greater than the one provided at the start of the algorithm, let’s call it CC. Similarly, since we have nn number of different coins, the maximum variable will therefore be bounded by nn. Therefore, we will have, at most C×nC\times n subproblems. Therefore, the time complexity to evaluate these problems would be O(Cn)O(Cn).

Space complexity#

The space required to hold the results of these subproblems would be C×nC\times n, so the space complexity is O(Cn)O(Cn) as well.

Bottom-up solution#

Now let’s look at the bottom-up dynamic programming approach to solving this problem. The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic programming problems. To make up an amount using nn coins, we just need to iteratively count the ways in which we can either make the amount using the nthn^{th} coin or without using it.

Here, we first create a table dpdp of size (C+1)×(n)(C+1) \times (n), where CC is the target amount and nn is the number of coins we have. The row signifies the amount, ii, at any given point, and the column signifies the values of the available coins, jj. Each cell of our table, dp[i][j]dp[i][j], represents the number of ways to make the amount ii using coins 0,1,2,...j0,1, 2, ... j.

First, as per the base case, for the amount 00, i=0i=0 , we add "11s" in the first row of the table. This is because there is always one way to make an amount of 00 by using none of the available coins, that is, we choose not to pick any of the coins 11, 22, or 33.

Next, we fill up each cell of our table using the unbounded knapsack dynamic programming pattern. In the pattern, for each cell, we need the sum of two values we get from two of our choices:

  • Use the coin: We only use the coin if icoins[j]>=0i - coins[j] >= 0. If we pick coins[j]coins[j], provided icoins[j]>=0i - coins[j] >= 0, then the amount ii reduces by coins[j]coins[j]. Now, we need the number of ways to make this remaining amount using coins 0,1,2,...j0, 1, 2, ...j. We already have this value present at dp[icoins[j]][j]dp[i - coins[j]][j].

  • Don't use the coin: We don't use the coin if icoins[j]<0i - coins[j] < 0. If we don't pick coins[j]coins[j], given icoins[j]<0i - coins[j] < 0, then we have to figure out the number of ways to make the amount ii using only coins 0,1,2,...j10, 1, 2, ...j - 1. This value is already present at dp[i][j1]dp[i][j-1].

Let’s look at the following illustration to get a better understanding of the algorithm:

Created with Fabric.js 3.6.6 1 2 3 0 1 2 0 1 2 3 4 Amount (i) Coins Index (j) Let's find the number of waysto make the amount 4 using the coins 1, 2 and 3.First, create a table, let's say dp.

1 of 10

Created with Fabric.js 3.6.6 1 2 3 0 1 2 0 1 1 1 1 2 3 4 Coins Amount (i) Index (j) For the base case, that is, amount is 0, we set all the values in the first row, i = 0,to 1.

2 of 10

Created with Fabric.js 3.6.6 1 2 3 0 1 2 0 1 1 1 1 1 2 3 4 Coins Index (j) Amount (i) i - coins[j] >= 01 - 1 >= 00 >= 0dp[i][j] = use coin + don't use coindp[i][j] = dp[i - coins[j]][j] + 0dp[1][0] = dp[0][0] + 0dp[1][0] = 1 + 0 = 1

3 of 10

Created with Fabric.js 3.6.6 1 2 3 0 1 2 0 1 1 1 1 1 1 2 3 4 Coins Amount (i) Index (j) i - coins[j] < 01 - 2 < 0-1 < 0dp[i][j] = use coin + don't use coindp[i][j] = 0 + dp[i][j-1]dp[1][1] = 0 + dp[1][0]dp[1][1] = 0 + 1 = 1

4 of 10

Created with Fabric.js 3.6.6 1 2 3 0 1 2 0 1 1 1 1 1 1 1 2 3 4 Coins Amount (i) Index (j) i - coins[j] < 01 - 3 < 0-2 < 0dp[i][j] = use coin + don't use coindp[i][j] = 0 + dp[i][j-1]dp[1][2] = 0 + dp[1][1]dp[1][2] = 0 + 1 = 1

5 of 10

Created with Fabric.js 3.6.6 1 2 3 0 1 2 0 1 1 1 1 1 1 1 2 1 3 4 Coins Amount (i) Index (j) i - coins[j] >= 02 - 1 >= 01 >= 0dp[i][j] = use coin + don't use coindp[i][j] = dp[i - coins[j]][j] + 0dp[2][0] = dp[1][0] + 0dp[2][0] = 1 + 0 = 1

6 of 10

Created with Fabric.js 3.6.6 1 2 3 0 1 2 0 1 1 1 1 1 1 1 2 1 2 3 4 Coins Amount (i) Index (j) i - coins[j] >= 02 - 2 >= 00 >= 0dp[i][j] = use coin + don't use coindp[i][j] = dp[i - coins[j]][j] + dp[i][j-1]dp[2][1] = dp[0][1] + dp[2][0]dp[2][1] = 1 + 1 = 2

7 of 10

Created with Fabric.js 3.6.6 Coins Use the same pattern tofill up the rest of the cells. Amount (i) Index (j) 1 2 3 0 1 2 0 1 1 1 1 1 1 1 2 1 2 2 3 1 2 3 4 1 3

8 of 10

Created with Fabric.js 3.6.6 1 2 3 0 1 2 0 1 1 1 1 1 1 1 2 1 2 2 3 1 2 3 4 1 3 4 Coins Amount (i) Index (j) i - coins[j] >= 04 - 3 >= 01 >= 0dp[i][j] = use coin + don't use coindp[i][j] = dp[i - coins[j]][j] + dp[i][j-1]dp[4][2] = dp[1][2] + dp[4][1]dp[4][2] = 1 + 3 = 4

9 of 10

Created with Fabric.js 3.6.6 Coins Amount (i) Index (j) 1 2 3 0 1 2 0 1 1 1 1 1 1 1 2 1 2 2 3 1 2 3 4 1 3 4 After all the calculations using thispattern, the total ways to make theamount 4 using coins 1, 2 and 3 is 4,that is, the value in the last cellof our table.

10 of 10

Let's have a look at the code for the bottom-up approach as well.

Coin Change II using tabulation

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

As apparent from the visualization as well, we are iterating over a table of size C×nC\times n , where CC is the target amount, and nn is the number of coins. Therefore, the time complexity of this algorithm is O(Cn)O(Cn).

Space complexity#

The space complexity of this algorithm is O(Cn)O(Cn).

Can we do better?#

You must have noticed in the above algorithm that to fill up a column, we only require the previous column’s values; that is, for filling the column against the nthn^{th} coin, we require the values from the previous column representing the (n1)th(n-1)^{th} coin. Therefore, there is no point in storing all the previous (n2)(n-2) columns.

We can further improve this approach by using a lookup array of length amount+1amount + 1 instead of creating a table. Next, we update this array for each coin using the same calculation which we used earlier.

The time complexity would remain the same, O(Cn)O(Cn), because we still have to do the calculation for each value amount and each coin. The space complexity, however, reduces to O(C)O( C ) since we are only maintaining an array of the size amount+1amount + 1.

Minimum Coin Change

Introduction to Recursive Numbers